# 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
# 
#  如果数组中不存在目标值 target，返回 [-1, -1]。 
# 
#  进阶： 
# 
#  
#  你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [5,7,7,8,8,10], target = 8
# 输出：[3,4] 
# 
#  示例 2： 
# 
#  
# 输入：nums = [5,7,7,8,8,10], target = 6
# 输出：[-1,-1] 
# 
#  示例 3： 
# 
#  
# 输入：nums = [], target = 0
# 输出：[-1,-1] 
# 
#  
# 
#  提示： 
# 
#  
#  0 <= nums.length <= 105 
#  -109 <= nums[i] <= 109 
#  nums 是一个非递减数组 
#  -109 <= target <= 109 
#  
#  Related Topics 数组 二分查找 
#  👍 1248 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        low = self.binary_search(nums, target, True)
        high = self.binary_search(nums, target, False) - 1
        if low <= high < len(nums) and nums[low] == target and nums[high] == target:
            return [low, high]
        return [-1, -1]

    def binary_search(self, nums: List[int], target: int, low: bool) -> int:
        if not nums:
            return len(nums)
        l, r = 0, len(nums) - 1
        ans = len(nums)
        while l <= r:
            mid = (l + r) // 2
            no_low_left = not low and target < nums[mid]
            low_left = low and target <= nums[mid]
            if no_low_left or low_left:
                r = mid - 1
                ans = mid
            else:
                l = mid + 1
        return ans



# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 二分法, 查找第一个target元素, 和第一个大于target元素-1
# 只剩一个元素时, 必然是第一个符合条件的元素
# 校验找到的元素合法
#     def searchRange(self, nums: List[int], target: int) -> List[int]:
#         low = self.binary_search(nums, target, True)
#         high = self.binary_search(nums, target, False) - 1
#         if low <= high < len(nums) and nums[low] == target and nums[high] == target:
#             return [low, high]
#         return [-1, -1]
#
#     def binary_search(self, nums: List[int], target: int, low: bool) -> int:
#         if not nums:
#             return len(nums)
#         l, r = 0, len(nums)
#         ans = len(nums)
#         while l <= r:
#             mid = (l + r) // 2
#             no_low_left = not low and target < nums[mid]
#             low_left = low and target <= nums[mid]
#             if no_low_left or low_left:
#                 r = mid - 1
#                 ans = mid
#             else:
#                 l = mid + 1
#         return ans
if __name__ == '__main__':
    s = Solution()
    nums1 = [5, 7, 7, 8, 8, 10]
    r1 = s.searchRange(nums1, 8)
    assert r1 == [3, 4], r1
